use std::collections::HashMap;

const DENOMINATIONS_BY_DESC: [u32; 8] = [100, 50, 30, 20, 10, 5, 2, 1]; // order by descending

pub fn dp_rec_mc(amount: u32) -> u32 {
    let mut cache = HashMap::new();
    min_changes_memo(amount, &DENOMINATIONS_BY_DESC, &mut cache)
        .expect("can't make change for the amount")
}

fn min_changes_memo<'a>(
    amount: u32,
    denoms_by_desc: &'a [u32],
    cache: &mut HashMap<(u32, &'a [u32]), u32>,
) -> Option<u32> {
    fn inner<'a>(
        amount: u32,
        denoms_by_desc: &'a [u32],
        cache: &mut HashMap<(u32, &'a [u32]), u32>,
    ) -> Option<u32> {
        match *denoms_by_desc {
            [] => None,
            [last] => (amount % last == 0).then(|| amount / last),
            [first, ref rest @ ..] => {
                if amount % first == 0 {
                    // Correct (optimal) only when denominations are ordered by descending.
                    Some(amount / first)
                } else {
                    (0..=(amount / first))
                        .filter_map(|first_count| {
                            min_changes_memo(amount - first_count * first, rest, cache)
                                .map(|min| first_count + min)
                        })
                        .min()
                }
            }
        }
    }

    if amount == 0 {
        return Some(0);
    }
    match cache.get(&(amount, denoms_by_desc)) {
        Some(&min) => Some(min),
        None => {
            let min = inner(amount, denoms_by_desc, cache)?;
            cache.insert((amount, denoms_by_desc), min);
            Some(min)
        }
    }
}
